//https://leetcode.cn/problems/longest-increasing-subsequence/submissions/532950396/
//300
//最长递增子序列
class Solution {
    public int lengthOfLIS(int[] nums) {

        int len = nums.length;
        //定义dp[i]为以nums[i]为起始节点最长递增子序列的长度
        int[] dp = new int[len];

        dp[0] = 1;
        backtrace(dp, nums, 0);

        int max = dp[0];
        for(int i = 0; i < len; i++){
            max = Math.max(dp[i], max);
        }

        return max;
    }

    void backtrace(int[] dp, int[] nums, int index){
        int len = nums.length;
        if(index >= len ){
            //结束了。
            return ;
        }

        dp[index] = 1;
        for(int i = index -1; i >= 0; i--){
            //查找左侧比自己小的nums[i]
            if(nums[i] < nums[index]){
                dp[index] = Math.max(dp[i] + 1, dp[index]);
            }
        }

        backtrace(dp, nums, index+1);
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        //也可以不使用递归，直接使用双层for循环解决问题
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = 1;

        for(int i = 0; i < len; i++){
            dp[i] = 1;
            for(int j = 0; j <i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int max = dp[0];
        for(int i = 0; i < len; i++){
            max = Math.max(max, dp[i]);
        }

        return max;

    }


}